package com.yeung.exam;

import java.util.Scanner;

/**
 * 0 1 12 -1 -1 -1
 * -1 0 9 3 -1 -1
 * -1 -1 0 -1 5 -1
 * -1 -1 4 0 13 15
 * -1 -1 -1 -1 0 4
 * -1 -1 -1 -1 -1 0
 */
public class 最短路径 {
    static final int MAX = 20000000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] ns = sc.nextLine().split(" ");
        int[] nodes = toInt(ns);
        int[][] graph = new int[nodes.length][nodes.length];
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i] == -1)
                graph[0][i] = MAX;
            else
                graph[0][i] = nodes[i];

        }
        //n-1行的数据
        for (int k = 1; k < nodes.length; k++) {
            String[] line = sc.nextLine().split(" ");
            int[] ints = toInt(line);
            for (int i = 0; i < ints.length; i++) {
                if (ints[i] == -1)
                    graph[k][i] = MAX;
                else
                    graph[k][i] = ints[i];
            }
        }
        //图数据准备好
        int[] dist = dijsktra(graph);
        for (int i : dist) {
            System.out.print(i + " ");
        }
    }

    public static int[] dijsktra(int[][] edge) {
        //得到顶点个数
        int vartex = edge.length;
        //标记
        int flag = 0;
        //记录某个顶点有没有访问到
        int[] mark = new int[vartex];
        //这里求的是从第一个顶点到其它顶点的最短距离
        mark[0] = 1;
        int[] distance = new int[vartex];
        //最开始默认的都是边的值，这里传进来就得事先做好处理，比如两个顶点之间不可达，那么久应该赋值为一个很大的数
        for (int i = 0; i < vartex; i++) {
            distance[i] = edge[0][i];
        }
        //核心代码
        for (int i = 1; i < vartex; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < vartex; j++) {
                if (mark[j] == 0 && distance[j] < min) {
                    min = distance[j];
                    flag = j;
                }
            }
            mark[flag] = 1;
            for (int k = 0; k < vartex; k++) {
                if (distance[k] > (distance[flag] + edge[flag][k])) {
                    distance[k] = distance[flag] + edge[flag][k];
                }
            }

        }
        return distance;
    }

    private static int[] toInt(String[] arr) {
        int[] tmp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            tmp[i] = Integer.parseInt(arr[i]);
        }
        return tmp;
    }
}

